package 递归回溯;

public class JZ46把数字翻译成字符串 {

    /**
     * 给定一个数字，我们按照如下规则把它翻译为字符串：
     * 0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
     * 一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
     *
     * 示例 1:
     * 输入: 12258
     * 输出: 5
     * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
     *  
     * 提示：
     * 0 <= num < 231
     */

    /**
     * 动态规划解法
     * 12222->1,2,3,5,8
     * 可以看出规律 如果第i位符合,[i]=[i-2]+[i-1]
     *            不符合,[i]=[i-1]
     */
    public int translateNumDP(int num) {

        String strNum = String.valueOf(num);

        if(strNum.length()<2){
            return 1;
        }

        int[] dp=new int[strNum.length()];
        dp[0]=1;
        if(isValied(1,strNum)) {
            dp[1] = 2;
        }else{
            dp[1] = 1;
        }

        //向后吃的
        for (int i = 2; i < strNum.length(); i++) {

            if(isValied(i,strNum)){
                dp[i]=dp[i-1]+dp[i-2];
            }else{
                dp[i]=dp[i-1];
            }

        }

        return dp[strNum.length()-1];
    }

    private boolean isValied(int index,String str){
        //向前看的
        if(index==0){
            return false;
        }
        if(str.charAt(index-1)=='1'){
            return true;
        }
        if(str.charAt(index-1)=='2'&&str.charAt(index)<='5'){
            return true;
        }
        return false;
    }

    private String strNum;
    private int count;

    /**
     * 递归解法
     */
    public int translateNum(int num) {

        this.strNum = String.valueOf(num);
        dfs(0);

        return count;
    }

    private void dfs(int index){

        if(index==strNum.length()){
            count++;
            return;
        }

        //单独吃一个
        dfs(index+1);
        //一次吃两个(审查后)
        if(strValidJump(index)){
            dfs(index+2);
        }

    }

    private boolean strValidJump(int index){
        if(index+1>=strNum.length()){
            return false;
        }
        if(strNum.charAt(index)>='3'){
            return false;
        }
        if(strNum.charAt(index)=='0'){
            return false;
        }
        if(strNum.charAt(index)=='2'&&strNum.charAt(index+1)>'5'){
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        JZ46把数字翻译成字符串 jz=new JZ46把数字翻译成字符串();
        int result = jz.translateNum(12261);
        System.out.println(result);
        System.out.println(jz.translateNumDP(12261));
    }



}
